'''
https://leetcode.cn/problems/loud-and-rich/description/
'''

from collections import defaultdict, deque
from typing import List


class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        # 有向无环图
        graph = defaultdict(list)
        # 入度，以及拓扑排序的（bfs队列实现）
        indegrees = [0] * n
        q = deque()

        for u, v in richer:
            graph[u].append(v)
            indegrees[v] += 1
        for i, indegree in enumerate(indegrees):
            if indegree == 0:
                q.append(i)

        ans = [i for i in range(n)]
        while q:
            u = q.popleft()
            for v in graph[u]:
                # 比u有钱的一定比v有钱
                # 在这里最安静的，有没有比比v的答案中更安静
                ans[v] = ans[u] if quiet[ans[u]] <= quiet[ans[v]] else ans[v]
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    q.append(v)
        return ans

richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]]
quiet = [3,2,5,4,6,1,7,0]
print(Solution().loudAndRich(richer, quiet))